package A一周刷爆LeetCode.A基础班.G图;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author wei.zhao
 * @description: 单元最短路径算法
 * @date 2022年03月08日 23:21
 */
public class Code06_Dijkstra {

    public static HashMap<Node, Integer> dijkstra(Node head) {
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        // 已经确认的点
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = head;
        while (minNode != null) {
            for (Edge edge : minNode.edges) {
                if (!distanceMap.containsKey(edge.to)) {
                    distanceMap.put(edge.to, distanceMap.get(minNode) + edge.weight);
                } else {
                    distanceMap.put(edge.to, Math.min(distanceMap.get(minNode), distanceMap.get(minNode) + edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    // 找尚未选择的最小的节点
    private static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes) {
        Node minNode = null;
        Integer minDistance = Integer.MAX_VALUE;
        for (Node node : distanceMap.keySet()) {
            if (distanceMap.get(node) < minDistance && !selectedNodes.contains(node)) {
                minNode = node;
                minDistance = distanceMap.get(node);
            }
        }
        return minNode;
    }

}
